#include <cstdio>
#include <algorithm>

#define V 30001 
#define N 30

using namespace std; 

int v[N]; 	//price
int w[N]; 	//priority
int n, m; 

int a[V]; 	// index is price, 
				// value is maximum product that can be bought in 

int main()
{
	int h, i, j, k, p, t, s; 
	int res=0; 
	
	freopen("p1060.in", "r", stdin); 

	scanf("%d %d", &m, &n); 
	for (i=0; i<n; i++) {
		scanf("%d %d", &v[i], &w[i]); 
		w[i] = w[i]*v[i]; 
	}

	for (i=0; i<n; i++) {
		for (j=m; j>=v[i]; j--) { 
			a[j] = max(a[j], a[j-v[i]] + w[i]); 
		}
	}
	printf("%d\n", a[m]); 
	return 0; 
}


